package com.camus.algorithm.impl;

import java.util.Arrays;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.camus.algorithm.SubsetAlgorithm4Int;

/**
 * 递归优化(数据有序的场景剪枝优化)算法求目标和的子集
 * 
 * @author jie.deng
 *
 */
public class SubsetAlgorithmOfSortPruningRecursion4Int implements SubsetAlgorithm4Int {
	
	private static final Logger log = LoggerFactory.getLogger(SubsetAlgorithmOfSortPruningRecursion4Int.class);

	@Override
	public int[] findSubsetOfTargetSum(int[] candidateArr, int target) {
		counter.remove();
		// 先排序，方便后面有针对性地剪枝
		Arrays.sort(candidateArr);

		int len = candidateArr.length;
		// 前缀和
		int[] prefixSumArr = new int[len];
		prefixSumArr[0] = candidateArr[0];
		for (int i = 1; i < len; i++) {
			prefixSumArr[i] = prefixSumArr[i - 1] + candidateArr[i];
		}

		// fail fast
		int min = candidateArr[0];
		int max = candidateArr[len - 1];
		int sum = prefixSumArr[len - 1];
		if (min >= 0) {
			// 所有元素都是正数
			if (min > target) {
				// 且最小元素大于目标和
				return null;
			}
			if (sum < target) {
				// 且所有元素之和仍然小于目标和
				return null;
			}
		}
		if (max <= 0) {
			// 所有元素都是负数，
			if (max < target) {
				// 且最大元素小于目标和
				return null;
			}
			if (sum > target) {
				// 且所有元素和仍然大于目标和
				return null;
			}
		}

		// 逐层递归
		int[] subsetArr = findSubsetOfTargetSum(candidateArr, target, 0, new boolean[len], 0, prefixSumArr);
		log.info("入参paramArr={},target={},resultArr={},时间复杂度={}", Arrays.toString(candidateArr), target, subsetArr,
				counter.get());
		return subsetArr;
	}

	public int[] findSubsetOfTargetSum(int[] candidateArr, int target, int nextIdx, boolean[] flagArr, int curSum,
			int[] prefixSumArr) {
		counter.set(counter.get().intValue() + 1);
		// 递归终止条件
		if (curSum == target) {
			return filterSubset(candidateArr, flagArr);
		}
		int len = candidateArr.length;
		if (nextIdx >= len) {
			return null;
		}

		// 根据数据升序的特点，提前结束递归调用的情况
		if (candidateArr[nextIdx] >= 0) {
			// 剩余所有元素都是正数
			if (curSum > target) {
				// 当前已选择的元素之和已经大于目标和
				return null;
			}
			int maxSum = curSum + prefixSumArr[len - 1];
			if (nextIdx > 0) {
				maxSum = maxSum - prefixSumArr[nextIdx - 1];
			}
			if (maxSum < target) {
				// 当前已选择的元素之和+剩余的所有元素之和仍然小于目标和
				return null;
			}
		}

		// 处理当层逻辑
		// 对于candidateArr[nextIdx]，有两种选择：a.包含 b.不包含
		// a.结果集中包含当前元素
		flagArr[nextIdx] = true;
		int[] result = findSubsetOfTargetSum(candidateArr, target, nextIdx + 1, flagArr, curSum + candidateArr[nextIdx],
				prefixSumArr);
		if (result != null) {
			return result;
		}

		// b.结果集中不包含当前元素
		flagArr[nextIdx] = false;
		return findSubsetOfTargetSum(candidateArr, target, nextIdx + 1, flagArr, curSum, prefixSumArr);
	}

	private int[] filterSubset(int[] candidateArr, boolean[] flagArr) {
		int len = candidateArr.length;

		int size = 0;
		for (int i = 0; i < len; i++) {
			if (flagArr[i]) {
				size++;
			}
		}

		int[] subsetArr = new int[size];
		for (int i = len - 1; i >= 0; i--) {
			if (flagArr[i]) {
				subsetArr[--size] = candidateArr[i];
			}
		}
		return subsetArr;
	}

}
